<head>
  <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>План лекций</title>
  <link href=styles/styles.css rel="stylesheet" type="text/css">
</head>
<h2>Теория чисел (base)</h2>
<ol>
  <li>Разложение числа на простые множители за O(n<sup>1/2</sup>)</li>
  <li>Решето Эратосфена</li>
  <ol>
    <li>Алгоритм, нахождение минимального простого делителя для каждого числа</li>
    <li>Доказательство времени работы O(nloglogn)</li>
    <li>Реализация за O(n)</li>
  </ol></li>
  <li>Разные мультипликативные функции, их вычисление</li>
  <ol>
    <li>Функция Эйлера, &phi;(n) &minus; количество чисел взаимнопротых с данным</li>
    <li>d(n) &minus; количество делителей числа</li>
    <li>&sigma;(n) &minus; сумма всех делителей числа</li>
    <li>d(n) и &sigma;(n) считаются за O(n<sup>1/2</sup>) циклом for</li>
    <li>Точные формулы для всех перечисленных функций, их вычисление за O(разложения на множители)</li>
    <li>Чтобы посчитать функции для всех k=1..n за O(n), воспользуемся решетом Эратосфена и мультипликативностью</li>
  </ol></li>
  <li>Обратные по модулю</li>
  <ol>
    <li>Теорема Эйлера и малая теорема Ферма, доказательство</li>
    <li>Обратное к числу возведением в степень</li>
    <li>Деление по модулю</li>
    <li>Возведение в степень за O(logn)</li>
    <li>Умножение через сложение за O(logn) (когда числа до 10<sup>18</sup> умножаются по модулю, это актуально)</li>
    <li>Умножение за O(1) через вещественные числа (нужно числа до 10<sup>18</sup> умножить по модулю)</li>
  </ol></li>
  <li>Алгоритм Евклида</li>
  <ol>
    <li>Вычисление gcd (через вычитание, через взятие по модулю)</li>
    <li>Вычисление gcd для длинных чисел (через сложение, вычитание, деление на два)</li>
    <li>Расширенный алгоритм Евклида, решение уравнения ax + by = gcd(a, b)</li>
    <li>Деление по непростому модулю за O(logn) с помощью алгоритма Евклида</li>
    <li>Решение уравнения ax + by = c в целых числах, получение всего класса решений</li>
    <li>Решение уравнения ax + by = c в натуральных числах (a, b, c, x, y > 0)</li>
  </ol></li>
  <li>Поиск всех обратных по модулю простого p за O(p)</li>
</ol>
